// https://www.lintcode.com/problem/3sum/

public class Solution {
    /**
     * @param numbers: Give an array numbers of n integer
     * @return: Find all unique triplets in the array which gives the sum of zero.
     */
    public List<List<Integer>> threeSum(int[] numbers) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(numbers);
        for (int i = 0; i < numbers.length; ++i) {
            if (i > 0) {
                if (numbers[i] == numbers[i - 1]) {
                    continue;
                }
            }
            twoSum(ret, numbers, -numbers[i], i + 1);
        }
        return ret;
    }
    
    private void twoSum(List<List<Integer>> ret, int[] numbers, int target, int start) {
        int end = numbers.length - 1;
        while (start < end) {
            int x = numbers[start];
            int y = numbers[end];
            if ((x + y) == target) {
                List<Integer> v = new ArrayList<>();
                v.add(-target);
                v.add(x);
                v.add(y);
                ret.add(v);
                ++start;
                --end;
                while ((start < end) && (numbers[start] == x)) {
                    ++start;
                }
                while ((start < end) && (numbers[end] == y)) {
                    --end;
                }
            } else if ((x + y) < target) {
                ++start;
            } else {
                --end;
            }
        }
    }
}